Tutorial Intro

PriorityQueue is an unordered collection that follows a priority-based approach. Elements are inserted and retrieved based on their natural ordering (if they implement Comparable) or a custom comparator provided during creation. The element with the highest priority (smallest for default natural ordering) is always retrieved first.

Characteristics of PriorityQueues

✦ Ordering: Elements are not stored in any specific insertion order. ✦ Priorities: Elements have priorities that determine the retrieval order. The element with the highest priority is retrieved first. ✦ Functionality: PriorityQueues primarily focus on add (insert) and poll (remove and return the highest priority element) operations. ✦ Implementations: Java's PriorityQueue uses a heap data structure (often a min-heap) for efficient priority management. ✦ Retrieval: The poll() or remove() methods always return the element with the highest priority. ✦ Modification: You can add elements to the queue, but their position will be determined by their priority relative to existing elements.

Declaring PriorityQueue

Similar to other collection classes, declaring a PriorityQueue involves creating a reference variable:

Declaring PriorityQueue PriorityQueue<DataType> queueName;

Explanation : PriorityQueue: This specifies the class you're using. <DataType>: Placeholder for the data type the queue will store. This data type must be comparable (implement the Comparable interface) or you need to provide a custom comparator during creation. queueName: The name for your reference variable.

Initialization

1.Creating an empty PriorityQueue:

Creating an empty PriorityQueue:PriorityQueue<String> name = new PriorityQueue<>();

Note: In this case, elements must be comparable (e.g., String implements Comparable).

2. Creating a PriorityQueue with initial elements (Collection initializer):

Creating a PriorityQueue with initial elements PriorityQueue<Integer> numbers = new PriorityQueue<>() {{ add(10); add(20); add(5); }};

Note: Here, Integer implements Comparable, so it works inherently.

3. Custom Comparator for PriorityQueue: If you want to sort elements based on a criteria different from their natural ordering, you can provide a custom comparator during creation.

PriorityQueue custom comparator syntax Comparator<Product> comparator = new Comparator<Product>() { @Override public int compare(Product p1, Product p2) { //code to set priority } }; PriorityQueue<Product> products = new PriorityQueue<>(comparator); products.add(new Product(1, "Laptop", 599.99)); products.add(new Product(2, "Headphones", 79.95)); products.add(new Product(3, "Monitor", 199.99));

Explanation : In this example, a custom comparator is created to sort Product objects by price in ascending order. The poll() method repeatedly removes and returns the product with the lowest price (highest priority in this case).

Characteristics: ⯁ PriorityQueue prioritizes elements based on their natural ordering or a custom comparator. ⯁ It doesn't allow direct access to elements based on their index. Use retrieval methods like poll() or remove(). ⯁ Adding elements modifies the queue's internal order based on priorities.

Important Methods in PriorityQueue

add(element): Inserts an element into the queue according to its priority. poll(): Removes and returns the element with the highest priority (smallest for default natural ordering). peek(): Returns the element with the highest priority (without removing it). isEmpty(): Checks if the queue is empty. clear(): Removes all elements from the queue.

Natural Ordering vs. Custom Comparator

By default, PriorityQueue uses the element's natural ordering (if it implements Comparable). The smallest element is considered the highest priority.You can optionally provide a custom Comparator during creation to define your own priority logic.

Examples of priorityqueue

1. Priorityqueue (natural ordering) example

Priorityqueue simple example(natural ordering) import java.util.PriorityQueue; public class Main{ public static void main(String args[]){ PriorityQueue<Integer> numbers = new PriorityQueue<>(); numbers.add(11); numbers.add(2); numbers.add(15); numbers.add(9); numbers.add(7); numbers.add(5); numbers.add(8); System.out.println(numbers); } }

Output

[2, 7, 5, 11, 9, 15, 8]

This code creates a PriorityQueue for integers. Since Integer implements Comparable, elements are retrieved in their natural order (ascending order for integers). This is a simple example where priority directly corresponds to the element's value.

2. Prioritizing Custom Objects with Custom Comparator

Priority queue custom comparator example in Java import java.util.*; class Product { int id; String name; double price; public Product(int id, String name, double price) { this.id = id; this.name = name; this.price = price; } } public class Main { public static void main(String[] args) { Comparator<Product> comparator = new Comparator<Product>() { @Override public int compare(Product p1, Product p2) { return Double.compare(p1.price, p2.price); // Sort by price (ascending) } }; PriorityQueue<Product> products = new PriorityQueue<>(comparator); products.add(new Product(1, "Laptop", 599.99)); products.add(new Product(2, "Headphones", 79.95)); products.add(new Product(3, "Monitor", 199.99)); while (!products.isEmpty()) { Product product = products.poll(); // Get product with lowest price System.out.println("ID: " + product.id + ", Name: " + product.name + ", Price: $" + product.price); } } }

Output

ID: 2, Name: Headphones, Price: $79.95 ID: 3, Name: Monitor, Price: $199.99 ID: 1, Name: Laptop, Price: $599.99

Explanation : This code defines a Product class and a custom comparator to sort Product objects by price in ascending order. The PriorityQueue prioritizes products based on this custom comparison, retrieving the one with the lowest price (highest priority) first. In Conclusion: PriorityQueue is a versatile collection for managing elements based on priorities. It's a good choice when you need to prioritize element processing or retrieval based on their importance. If order is not crucial and you only need efficient insertion and removal, consider using a queue implementation like LinkedList.

Tutorials